package algorithm.Sort;

import java.io.*;

/**
 * 随机选择快速排序;
 * 随机选取一个元素，以这个元素为标准进行快速排序;
 * 本类提供了基础版和荷兰国旗问题优化版两种快速排序;
 * 快速排序的关键在于为序列确定分区，因此两版算法的差异在于分区;
 * 本类采用ACM的IO方式
 */
public class QuickSort {

    public static int MAX=100001;
    public static int[] nums=new int[MAX];
    public static int n;

    public static void main(String[] args) throws IOException{

        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in=new StreamTokenizer(br);
        PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));

        in.nextToken();
        n=(int)in.nval;

        for(int i=0;i<n;i++){
            in.nextToken();
            nums[i]=(int)in.nval;
        }
        quickSort(0,n-1);
//        hollandQuickSort();
        for(int i=0;i<n-1;i++){
            out.print(nums[i]+" ");
        }
        out.print(nums[n-1]);

        out.flush();
        out.close();
        br.close();

    }

    public static void swap(int a,int b){
        int temp=nums[a];
        nums[a]=nums[b];
        nums[b]=temp;
    }

    /**
     * 把子数组分为小于等于x和大于x的两部分
     * 用i遍历数组，用a表示小于等于x区域的右边界
     * 当i遍历到小于等于x的元素时，就与a-1标定的元素交换
     * 用xi表示小于等于x区域最右边的元素，即左右区域的分界点
     * @param l
     * @param r
     * @param x
     * @return
     */
    public static int partition(int l,int r,int x){
        int a=l,xi=0;
        for(int i=l;i<=r;i++){
            if(nums[i]<=x){
                swap(i,a);
                if(nums[a]==x){
                    xi=a;
                }
                a++;
            }
        }
        swap(xi,a-1);
        return a-1;
    }

    /**
     * 经典递归版快速排序，容易爆栈
     * @param r
     * @param l
     */
    public static void quickSort(int l,int r){

        if(l>=r) return;

        int x=nums[l+(int)(Math.random()*(r-l+1))];
        int mid=partition(l,r,x);
        quickSort(l,mid-1);
        quickSort(mid+1,r);

    }

    /**
     * 荷兰国旗版本的分区方法操作的是下面这两个全局静态变量
     * start end表示与x相等区域的边界，都是闭的
     */
    public static int start;
    public static int end;

    /**
     * 荷兰国旗版本的分区方法
     * 将数组分为小于x，等于x，大于x的三个区域，对应有三个判断逻辑
     * @param l
     * @param r
     * @param x
     */
    public static void hollandFlagPartition(int l,int r,int x){

        start=l;
        end=r;
        //i是一个哨兵，只负责遍历元素
        int i=l;

        while(i<=end){
            if(nums[i]==x){
                i++;
            }else if(nums[i]<x){
                swap(start++,i++);
            }else{
                swap(i,end--);
            }
        }
    }

    /**
     * 荷兰国旗版本的随机选择快速排序
     * @param l
     * @param r
     */
    public static void hollandQuickSort(int l,int r){
        if(l>=r) return;

        //产生随机数的常数时间很大
        int x=nums[l+(int)(Math.random()*(r-l+1))];
        hollandFlagPartition(l,r,x);

        //在每一层递归中都需要用一个局部变量保存，防止它们被覆盖
        int first=start;
        int last=end;

        hollandQuickSort(l,first-1);
        hollandQuickSort(last+1,r);
    }

}
